package com.bwt.search;

import java.util.ArrayList;
import java.util.List;

/*注意: 使用二分查找的前提,该数组必须是要有序的*/
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000,1000,1000, 1234};
        List<Integer> index = binarySearch2(arr, 0, arr.length - 1, 1000);
        System.out.println(index);
    }

    /**
     * @param arr     数组
     * @param left    左索引
     * @param right   右索引
     * @param findVal 要查找的值
     * @return 返回值的下标, 没有找到就返回-1
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midValue = arr[mid];
        if (findVal < midValue) {
            return binarySearch(arr, left, mid - 1, findVal);
        }
        if (findVal > midValue) { // 向右递归
            return binarySearch(arr, mid + 1, right, findVal);
        }
        return mid;
    }

    /**
     * 思考题
     *  {1, 8, 110, 89, 1000,1000,1000, 1234} 当一个有序数组中
     *  有多个相同的数时,如何将所有的数值都查找对, 比如这里的1000
     *
     *  思路分析
     *  1. 在找到mid 索引值,不要马上返回
     *  2. 在 mid 索引值的左边扫描, 将所有满足1000 的元素的下标,加入到集合ArrayList
     *  3. 在 mid 索引值的右边扫描, 将所有满足1000 的元素的下标,加入到集合ArrayList
     *  4. 将ArrayList返回
     *
     */
    public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
        if (left > right) {
            return new ArrayList<>();
        }
        int mid = (left + right) / 2;
        int midValue = arr[mid];
        if (findVal < midValue) {
            return binarySearch2(arr, left, mid - 1, findVal);
        }
        if (findVal > midValue) { // 向右递归
            return binarySearch2(arr, mid + 1, right, findVal);
        }
        List<Integer> resList = new ArrayList<>();
        /**
         * 递归到最内部时, 此时的mid已经时为找到的下标的索引
         * 所有只需要看左右两边是不是相同的数字即可, 因为这是一个有序序列
         */
        int temp = mid - 1;
        while (true) {
            if (temp < 0 || arr[temp] != findVal) { //退出
                break;
            }
            // 否则就将temp 放入到集合中
            resList.add(temp);
            temp--; //左移temp
        }
        //放入中间值
        resList.add(mid);
        temp = mid + 1;
        while (true) {
            if (temp >arr.length-1 || arr[temp] != findVal) { //退出
                break;
            }
            // 否则就将temp 放入到集合中
            resList.add(temp);
            temp++; //左移temp
        }
        return resList;
    }
}

